145E - Lucky Queries - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

template<
    class T1, // answer value stored on nodes, no puede ser bool
    class T2, // lazy update value stored on nodes, no puede ser bool
    T1 merge(T1, T1), 
    void pushUpd(T2&, T2&, int, int, int, int), // push update value from a node to another
    void applyUpd(T2&, T1&, int, int)           // push update value from a node to its answer value
>
struct SegmentTreeLazy{
    vector<T1> ST;
    vector<T2> lazy;
    vector<bool> upd;
    int n;
    void build(int i, int l, int r, vector<T1>&values){
        if (l == r){
            ST[i] = values[l];
            return;
        }
        build(i << 1, l, (l + r) >> 1, values);
        build(i << 1 | 1, (l + r) / 2 + 1, r, values);
        ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
    }
    SegmentTreeLazy(vector<T1>&values){
        n = values.size();
        ST.resize(n << 2 | 3);
        lazy.resize(n << 2 | 3);
        upd.resize(n << 2 | 3, false);
        build(1, 0, n - 1, values);
    }
    void push(int i, int l, int r){
      if (upd[i]){
        applyUpd(lazy[i], ST[i], l, r);
        if (l != r){
          if (!upd[i << 1])
            lazy[i << 1] = lazy[i];
          else
            pushUpd(lazy[i], lazy[i << 1], l, r, l, (l + r) / 2);
          if (!upd[i << 1 | 1])
            lazy[i << 1 | 1] = lazy[i];
          else
            pushUpd(lazy[i], lazy[i << 1 | 1], l, r, (l + r) / 2 + 1, r);
          upd[i << 1] = 1;
          upd[i << 1 | 1] = 1;
        }
        upd[i] = false;
      }
    }
    void update(int i, int l, int r, int a, int b, T2 &u){
        if (l >= a and r <= b){
          if (!upd[i])
            lazy[i] = u;
          else
            pushUpd(u, lazy[i], a, b, l, r);
          upd[i] = true;
        }
        push(i, l, r);
        if (l > b or r < a) return;
        if (l >= a and r <= b) return;
        update(i << 1, l, (l + r) >> 1, a, b, u);
        update(i << 1 | 1, (l + r) / 2 + 1, r, a, b, u);
        ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
    }
    void update(int a, int b, T2 u){
        if (a > b){
            update(0, b, u);
            update(a, n - 1, u);
            return ;
        }
        update(1, 0, n - 1, a, b, u);
    }
    T1 query(int i, int l, int r, int a, int b){
        push(i, l, r);
        if (a <= l and r <= b)
            return ST[i];
        int mid = (l + r) >> 1;
        if (mid < a)
            return query(i << 1 | 1, mid + 1, r, a, b);
        if (mid >= b) 
            return query(i << 1, l, mid, a, b);
        return merge(query(i << 1, l, mid, a, b), query(i << 1 | 1, mid + 1, r, a, b));
    }
    T1 query(int a, int b){
        if (a > b){
            return merge(query(a, n - 1), query(0, b));
        }
        return query(1, 0, n - 1, a, b);
    }
};

struct node{
    int l44, l47, l74, l77;
    node(int val) : node(){
        if (val == 4)
            l44 = 1;
        else
            l77 = 1;
    }
    node(){
        l44 = l47 = l77 = l74 = 0;
    }
    node(int a, int b, int c, int d){
        l44 = a;
        l47 = b;
        l74 = c;
        l77 = d;
    }
};

node merge(node a, node b){
    return node(
            a.l44 + b.l44,
            max({a.l44 + b.l47, a.l44 + b.l77, a.l47 + b.l77}),
            max({a.l77 + b.l74, a.l77 + b.l44, a.l74 + b.l44}),
            a.l77 + b.l77
        );
}

void pushUpd(int &u1, int &u2, int l1, int r1, int l2, int r2){
    u2 ^= u1;
}

void applyUpd(int &u, node &v, int l, int r){
    if (u){
        swap(v.l44, v.l77);
        swap(v.l47, v.l74);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    string S;
    cin >> S;
    vector<node> a(n);
    for (int i = 0; i < n; i ++)
        a[i] = node(S[i] - '0');
    SegmentTreeLazy<node, int, merge, pushUpd, applyUpd> ST(a);

    while(m --){
        string q;
        cin >> q;
        if (q[0] == 'c'){
            node ans = ST.query(0, n - 1);
            cout << max({ans.l44, ans.l47, ans.l77}) << '\n';
        }
        else{
            int x, y;
            cin >> x >> y;
            x --; y --;
            ST.update(x, y, 1);
        }
    }

    return 0;
}